package org.gpf;


/**
 * 最大公约数
 * 
 * @author gaopengfei
 * @date 2015年5月30日 下午8:11:06
 */
public class GCD {

	/**
	 * 计算两个非负整数p和q的最大公约数： 若q是0，则最大公约数为p。 否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。
	 */
	public static int euclid(int p, int q) {

		if (q == 0)
			return p;
		int r = p % q;
		return euclid(q, r);
	}
}
